package com.leetcodehot.problems;

public class problems111 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 将整个递归过程看成是几个部分：
     * 一：基础情况，n为0或1的情况，即递归到底的退出条件
     * 二：超级操作，我们假设超级操作能够完成所有的剩余任务，难点在于设计合理的参数
     * 三：微操作，即超级操作完成的事情后，需要返回给上一层什么。
     */
    public int dfs(TreeNode root) {
        if (root.left == null && root.right == null) return 1;

        int res = Integer.MAX_VALUE;
        if (root.left != null) res = Math.min(res, dfs(root.left) + 1);
        if (root.right != null) res = Math.min(res, dfs(root.right) + 1);

        return res;
    }

    public int minDepth(TreeNode root) {
        return root == null ? 0 : dfs(root);
    }
}
